package alo.p6.work;

import alo.p6.BinaryTreeNode;

import java.util.LinkedList;
import java.util.Queue;

//查找二叉树是否包含值
public class FindInBinaryTree {
    //递归
    boolean findInBinaryTree(BinaryTreeNode root, int data){
        if (root==null) return false;
        else {
            if (data==root.getData())return true;
            else {
                return findInBinaryTree(root.getLeft(),data)||findInBinaryTree(root.getRight(),data);
            }
        }
    }
    //非递归，使用层序遍历
    boolean findInBinaryTree2(BinaryTreeNode root, int data){
        BinaryTreeNode temp;
        Queue<BinaryTreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            temp=queue.poll();
            if (data==temp.getData()) return true;
            if (temp.getLeft()!=null) queue.offer(temp.getLeft());
            if (temp.getRight()!=null) queue.offer(temp.getRight());
        }
        return false;
    }
}
